#if !defined( TREE_OPS_H)
#define  TREE_OPS_H

// standard headers
#include <iostream>

// boost headers
#include <boost/regex.hpp>

// component headers
#include <tree.h>
#include <matrix.h>

using boost::regex_search;

namespace bcpp_matrix
{
template <typename T> class t_dense_matrix;
typedef t_dense_matrix<float> t_dense_matrix_f;
}
namespace bcpp_tree_ops
{


//________________________________________________________________________________________

//	do_newhampshire_format_str

//________________________________________________________________________________________
struct do_newhampshire_format_str
{
	std::ostream& os;
	do_newhampshire_format_str(std::ostream& os_) :os(os_){}
	void operator()(const bcpp_tree::t_node* root);
	void recurse(const bcpp_tree::t_node* node);
};


//________________________________________________________________________________________

//	do_set_node_types

//________________________________________________________________________________________
enum eNODETYPE {eNONE, eTAX1, eTAX2, eTAX1_GENE, eTAX2_GENE, eTAX1_TAX2,
				eTAX1_GENE_ORTH, eTAX2_GENE_ORTH,
				eTAX1_ORTH, eTAX2_ORTH, eTAX1_TAX2_ORTH};
class do_set_node_types
{
	std::string 			tax1_matching_str;
	std::string 			tax2_matching_str;
	boost::regex			regex_tax1;
	boost::regex			regex_tax2;
	void set_node_type(bcpp_tree::t_node& node, eNODETYPE type)
											{	node_types[node.get_UID()] = type;	}
	void recurse(bcpp_tree::t_node* node);
	void tag_ortholog_decendents(bcpp_tree::t_node* node);
public:
	eNODETYPE get_node_type(bcpp_tree::t_node& node) const
											{	return node_types[node.get_UID()];	}
	std::vector<eNODETYPE>	node_types;
	do_set_node_types(const bcpp_tree::t_tree& tree,
						const std::string& s1, const std::string& s2);

};


//________________________________________________________________________________________

//	do_calculate_branch_lengths

//________________________________________________________________________________________
struct do_calculate_branch_lengths
{
	do_calculate_branch_lengths(const bcpp_tree::t_tree& tree);
	std::vector<float> lengths_to_leaves;
	std::vector<float> max_lengths_to_leaves;
	std::vector<float> lengths_to_root;
	float max_len_to_leaf;
	void recurse_len_to_root(bcpp_tree::t_tree::t_node_type* node);
	void recurse_len_to_leaves(bcpp_tree::t_tree::t_node_type* node,
						float& min_len_to_leaves, float& max_len_to_leaves);
};



//________________________________________________________________________________________

//	op_print_tree

//________________________________________________________________________________________
struct op_print_tree
{
	op_print_tree(	const bcpp_tree::t_tree&	tree,
				   	std::ostream&	 				os,
				   	const std::vector<float>&		lengths_to_leaves,
				   	const std::vector<float>&		lengths_to_root,
					const std::vector<eNODETYPE>&	node_types_,
					bool							nodes_only);
	const std::vector<float>&		lengths_to_leaves;
	const std::vector<float>&		lengths_to_root;
	const std::vector<eNODETYPE>&	node_types;
	std::ostream&					os;
	unsigned curr_level;

	void recurse(bcpp_tree::t_tree::t_node_type* node);
	void recurse_nodes_only(bcpp_tree::t_tree::t_node_type* node);
};



//________________________________________________________________________________________

//	op_dump_tree_data

//________________________________________________________________________________________
struct op_dump_tree_data
{
	op_dump_tree_data(	const bcpp_tree::t_tree&	tree,
				   	std::ostream&	 				os);
	std::ostream&					os;
	unsigned						curr_level;
	const bcpp_tree::t_tree&		tree;
	void							dump();
	void recurse(bcpp_tree::t_tree::t_node_type* node);
};



//________________________________________________________________________________________

//	op_tree_get_names

//________________________________________________________________________________________
template <typename ITER>
class op_tree_get_names
{
	const bcpp_tree::t_tree&		tree;
	ITER							iter;
public:
	op_tree_get_names(	const bcpp_tree::t_tree&		tree_,
						ITER							iter_):
			tree(tree_),
			iter(iter_){}
	void run(const bcpp_tree::t_tree::t_node_type* root = 0)
				{
					if (!root) recurse(*(tree.get_root()));
					else recurse(*root);
				};
	void recurse(const bcpp_tree::t_tree::t_node_type& node);
};

template <typename ITER>
void op_tree_get_names<ITER>::recurse(const bcpp_tree::t_tree::t_node_type& node)
{
	if (node.is_leaf())
	{
		*iter = node.get_name();
		++iter;
	}
	else
		for (unsigned i = 0; i < node.get_children_count(); ++i)
			recurse(*(node.get_child(i)));
}

template <typename ITER>
void get_tree_names(const bcpp_tree::t_tree& tree_, ITER iter)
{
	op_tree_get_names<ITER> do_get_names(tree_, iter);
	do_get_names.run();
}

//________________________________________________________________________________________

//	op_tree_names_to_short_names

//________________________________________________________________________________________
class op_tree_names_to_short_names
{
	unsigned					current_index;
	bcpp_tree::t_tree&			tree;
public:
	std::map<std::string,  std::string>	long_name_to_short_name;
	op_tree_names_to_short_names(	bcpp_tree::t_tree&	tree_,
									unsigned					current_index_ = 0):
					current_index(current_index_),
					tree(tree_){}
	void run(bcpp_tree::t_tree::t_node_type* root = 0)
				{
					if (!root) recurse(*(tree.get_root()));
					else recurse(*root);
				};
	void recurse(bcpp_tree::t_tree::t_node_type& node);
};


//________________________________________________________________________________________

//	op_print_tree_elaborate

//________________________________________________________________________________________
class op_print_tree_elaborate
{
	std::ostream&						os;
	const bcpp_tree::t_tree&		tree;
	unsigned							precision;
	unsigned							curr_level;
	mutable std::vector<char>			levels;
	const std::vector<float>&			lengths_to_leaves;
	const std::vector<float>&			lengths_to_root;
	const std::vector<eNODETYPE>&		node_types;
public:
	void print() const;
	void print(const bcpp_tree::t_tree::t_node_type& curr_node) const;
	op_print_tree_elaborate(const bcpp_tree::t_tree&		tree_,
							std::ostream& 						os_,
							const std::vector<float>&			lengths_to_leaves_,
							const std::vector<float>&			lengths_to_root_,
							const std::vector<eNODETYPE>&		node_types_ =
							std::vector<eNODETYPE>(),
							unsigned 							precision_ = 3):
			os(os_),
			tree(tree_),
			precision(precision_),
			curr_level(0),
			lengths_to_leaves(lengths_to_leaves_),
			lengths_to_root(lengths_to_root_),
			node_types(node_types_){}
	void operator()(const bcpp_tree::t_tree::t_node_type* root) const {print (*root);};
	void print_horizontal_lines() const
	{
		os << std::string(precision + 2, '-');
	}
	void print_vertical_lines() const
	{
		for (unsigned i = 0; i < levels.size(); ++i)
			os << std::string(precision + 1, ' ') << (levels[i] ? '|' : ' ');
	}
	void recurse(const bcpp_tree::t_tree::t_node_type& curr_node) const;
};



//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	do_collect_orthologs

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
struct t_gene_set
{
	std::vector<std::string>					genes;
	float										length;
};
inline void swap(t_gene_set& a, t_gene_set& b)
{
	std::swap(a.genes, b.genes);
	std::swap(a.length, b.length);
}
struct t_ortholog_data
{
	t_ortholog_data(): cnt_tax1(0), cnt_tax2(0){}
	std::vector<t_gene_set>						gene_sets;
	unsigned									cnt_tax1;
	unsigned									cnt_tax2;
	void sort_data();
};

struct do_collect_orthologs
{
	const std::vector<eNODETYPE>&		node_types;
	eNODETYPE		get_node_type(bcpp_tree::t_tree::t_node_type* node) const
								{ return node_types[node->get_UID()];}
	const std::vector<float>&			lengths_to_leaves;
	enum eORTH_TYPE{
					e_ORTH_1_TO_1,
					e_ORTH_1_TO_M,
					e_ORTH_M_TO_1,
					e_ORTH_M_TO_M,
					e_ORPH_TAX1,
					e_ORPH_TAX2,
					eORTH_TYPE_CNT};
	do_collect_orthologs(const std::vector<eNODETYPE>&		node_types_,
						const std::vector<float>&			lengths_to_leaves_
						)
			:node_types(node_types_),
			lengths_to_leaves(lengths_to_leaves_){}
	t_ortholog_data ortholog_sets[eORTH_TYPE_CNT];
	std::vector<bcpp_tree::t_tree::t_node_type*> tax1_genes;
	std::vector<bcpp_tree::t_tree::t_node_type*> tax2_genes;
	void store_genes(t_ortholog_data* store, float len = -1.0);
	void store_orthologs(bcpp_tree::t_tree::t_node_type* node);
	void store_orphaned_paralogs();
	void sort_data();
	void operator()(bcpp_tree::t_tree::t_node_type* node)	{	recurse(node);	store_orphaned_paralogs(); sort_data(); }
	void recurse(bcpp_tree::t_tree::t_node_type* node);
};

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	do_sum_sqrs

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
struct do_sum_sqrs
{
	do_sum_sqrs(const bcpp_matrix::t_dense_matrix_f & matrix_, const std::vector<float>& lengths_to_leaves_)
		:matrix(matrix_), sum_sqrs(0.0), cnt_non_null_data(0),
		lengths_to_leaves(lengths_to_leaves_){}

	const bcpp_matrix::t_dense_matrix_f&		matrix;
	std::deque<std::deque<unsigned> >	branches;
	float								sum_sqrs;
	float								avg_percent_stddev;
	unsigned							cnt_non_null_data;
	const std::vector<float>&			lengths_to_leaves;
	void operator()(bcpp_tree::t_tree::t_node_type* root);
	void recurse(bcpp_tree::t_tree::t_node_type* node, std::deque<unsigned>& parent_branch);
	void results(float& s, float& avg){s = sum_sqrs; avg = avg_percent_stddev;}
};


//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

//	do_sum_sqrs

//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
struct do_sum_sqrs2
{
	do_sum_sqrs2(const bcpp_matrix::t_dense_matrix_f & matrix_, const std::vector<float>& lengths_to_leaves_)
		:matrix(matrix_), sum_sqrs(0.0), cnt_non_null_data(0),
		lengths_to_leaves(lengths_to_leaves_){}
	const bcpp_matrix::t_dense_matrix_f&		matrix;
	std::deque<std::deque<unsigned> >	branches;
	float								sum_sqrs;
	float								avg_percent_stddev;
	unsigned							cnt_non_null_data;
	std::vector<float >				branch_lengths;
	std::vector<float >				branch_differences;
	const std::vector<float>&			lengths_to_leaves;
	void operator()(bcpp_tree::t_tree::t_node_type* root);
	void recurse(bcpp_tree::t_tree::t_node_type* node, std::deque<unsigned>& parent_branch);
	void results(float& s, float& avg){s = sum_sqrs; avg = avg_percent_stddev;}
};

//________________________________________________________________________________________

//	op_extract_branch_leaves

//________________________________________________________________________________________
struct op_extract_branch_leaves
{
private:
	void recurse(const bcpp_tree::t_tree::t_node_type* node);
	const bcpp_tree::t_tree::t_node_type& node;
public:
	op_extract_branch_leaves(const bcpp_tree::t_tree::t_node_type& node_):node(node_)
		{leaves.clear(); recurse(&node);}
	std::vector<const bcpp_tree::t_tree::t_node_type*>		leaves;
};

//
//	Set node labels to include children nodes hyphenated
//
struct op_set_labels_to_children_names
{
	bcpp_tree::t_tree&						tree;
	op_set_labels_to_children_names(bcpp_tree::t_tree& tree_):
		tree(tree_)
	{
		std::string label;
		recurse(tree.get_root(), label);
	}
	void recurse(bcpp_tree::t_node* node, std::string& label);

};


//	A species tree can be mapped on a gene tree to reveal gene duplication events and
//		gene losses (or missing data)
//	For each gene tree node, its position on the species tree and the number
//		of gene duplications/losses can be deduced by looking-up the corresponding
//		state of its child nodes.
//	Assumes a binary tree
//	Each gene node, thus should have
//		species_UID			the UID of the species tree node
//		cnt_missing_taxa    a running count of the missing taxa
//		cnt_duplications	a running count of the duplications
class t_species_tree_map
{
private:
	unsigned 									twice_taxa_count;
	std::vector<unsigned>							cnt_child_taxa_at_node;
	typedef std::deque<unsigned>::const_iterator deq_iter;
public:


	bcpp_tree::t_tree&						tree;

	// state of parent node given UID of children
	bcpp_matrix::t_dense_matrix<unsigned>    cnt_missing_taxa;
	bcpp_matrix::t_dense_matrix<unsigned>    cnt_duplications;
	bcpp_matrix::t_dense_matrix<unsigned>    parent_species_UID;

	// constructor calls calculating functor recursively
	t_species_tree_map(bcpp_tree::t_tree& tree_)
		:
		twice_taxa_count(tree_.get_leaf_count() * 2),
		cnt_child_taxa_at_node(tree_.get_node_count(), 0),
		tree(tree_),
		cnt_missing_taxa(tree_.get_node_count(), twice_taxa_count),
		cnt_duplications(tree_.get_node_count(), 1),
		parent_species_UID(tree_.get_node_count(), tree_.get_root()->get_UID())
		{
			std::deque<unsigned>	UIDs;
			unsigned				leaf_count;
			recurse(tree.get_root(), UIDs, leaf_count);
		}

	void recurse(bcpp_tree::t_node* node, std::deque<unsigned>& UIDs, unsigned& leaf_count);

};

};
#endif
